package com.yohann.algorithm.dynamicPlann;

/**
 * <p>
 * 动态规划-背包问题
 * </p>
 *
 * @author Yohann
 * @since 2021/1/17 17:18
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        //物品重量
        int[] weight = {1, 4, 3};
        //价值
        int[] value = {1500, 3000, 2000};
        //容量
        int capacity = 4;
        //物品个数
        int n = value.length;

        //v[i][j] 表示在前i个物品中能装入容量为j的最大价值
        int[][] v = new int[n + 1][capacity + 1];

        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                //容量不足 取左边值
                if (weight[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    //容量充足 上边与 （当前值 + 剩余容量的价值）*因为不可重复 所以取上一行
                    v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
                }
            }
        }

        System.out.println(v[n][capacity]);
    }
}